#include <coordinate.h>
#include <flat.h>
#include <sensor.h>
#include <solution.h>

bool filter(Flat&);
void backtracking(Flat&, Solution&, Solution&, Coordinate);

int main(int argc, char *argv[])
{
	Flat flat;

	flat.create(""); // STDIN, TODO: error al abrir archivo

	Solution solution, bestSolution;

	if(flat.check())
		backtracking(flat, solution, bestSolution, Coordinate(0,0));

	if(bestSolution.empty())
		cout << -1 << endl;
	else
		cout << bestSolution;

	return 0;
}

void backtracking(Flat &flat, Solution &solution, Solution &bestSolution, Coordinate currentCoordinate) {
	if(flat.isCovered()) {
		if(bestSolution.empty()) {
			bestSolution = solution;
			return;
		}
		
		if(!bestSolution.empty() && (solution.price() < bestSolution.price())) {
			bestSolution = solution;
			return;
		}
	}
	else {
		if(!bestSolution.empty() && (solution.price() >= bestSolution.price()))
			return;
	}

	if(currentCoordinate == CoordinateNIL)
		return;

	Coordinate availableCoordinate = flat.getAvailableTile( currentCoordinate );

	if(availableCoordinate == CoordinateNIL)
		return;

	for(int sensor = SENSOR_FD; sensor < SENSOR_NO; sensor++) {

		if(flat.isValidTile(availableCoordinate, sensor)) {

			flat.setSensor(availableCoordinate, sensor);
			solution.push(availableCoordinate, sensor);
		}
		else {
			continue;
		}

		backtracking(flat, solution, bestSolution, flat.getNextCoordinate(availableCoordinate));
		flat.clearSensor(availableCoordinate);
		solution.pop();
	}

	backtracking(flat, solution, bestSolution, flat.getNextCoordinate(availableCoordinate));
}